package com.LeeCode;

import java.util.Arrays;

/**
 * 最长回文子串
 */

public class Code005 {
    public static void main(String[] args) {
        String str = "aacabdkacaa";
        System.out.println(new Code005().longestPalindrome(str));
    }

    public String longestPalindrome(String s) {

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1, left = 0;
        for (int i = 0; i < n; i++) { // 初始化边界条件
            Arrays.fill(dp[i], true);
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                if (dp[i][j] && (maxLen < (j - i + 1))) {
                    maxLen = j - i + 1;
                    left = i;
                }
            }
        }
        return s.substring(left, left + maxLen);
    }
}
